D - Minimum Width - AtCoder Beginner Contest 319 の「単語を先頭から貪欲に配置する方法」が最適であることを確認したい
D - Minimum Width - AtCoder Beginner Contest 319]の「単語を先頭から貪欲に配置する方法」が最適であることの証明
単語を先頭から貪欲に（改行する必要がなければ改行せずに）配置するのが最適です。
証明
ある単語で改行する必要がないのに改行した最適解があるとします。 その単語以降を k 行以内に収めることができる場合、その単語で改行しなくても k 行以内に収めることができます。
よって、改行する必要がないところで改行をしない最適解があることが示されました。
この証明は、本当にアルゴリズムの最適性を証明しているのだろうか...？
最適解の存在を示したところで、貪欲法が最適解にたどり着くとは限らないような
(追記)
「改行しなくていいところでしない解」は一通りしかないので、それを踏まえるとどう足掻いても最適解になる？
こういうことか！！確かにこれで最適性が示せてる！appbird.icon
解の全体集合が
A:「改行しなくてもいいところでしている解」
B:「改行しなくてもいいところでしない解」
の二通りに分けられて、
この証明でAの方法で導かれた任意の解よりもBの方法が良い解を出す。
その上で、Bの解で導かれた解はただ一つしか存在しない
結果的にBの方法で得られる解が最適である
この証明で最適性が示せているのかが少し疑問に思ったので、最適性をしっかり示したい
別の方法でしっかり示したい
証明?概形
https://gyazo.com/c606ca0b122376c9bb4b7338e1a9380e
貪欲法における改行パターン①の位置が$ S_1, S_2, ..., S_Nにあったとして このうちの一つの改行$ L_iを消せば、区間$ L_{i-1}, L_{i+1}は幅$ Wを超過する。② ここで、残ったどの改行を(順序を保存しながら)どのように動かしても必ず幅Wを超過するような区間が出現する。③ ∵ 元々の改行が一つ消えているので、いずれかの区間には必ず貪欲法における行と非零個の単語(= 幅Wを超える区間)をまるごと一つ含むものがある (要証明だがおそらく正しい)
この改行の移動を有限回行えば、改行をN-1個含む任意の改行パターンを列挙することができる いずれでも幅Wを超過する区間が出現する。
よって、$ N-1個の改行パターンで制約(1行の幅 <= $ W)を満たすものは存在しない。 同様に、$ N-2個, $ N-3個, ... $ 1個の改行を含む任意のパターンでも制約は破られる $ f(W)行よりも小さい改行数で済むパターンは存在しない。
よって、$ f(W)行の貪欲法パターンが確かに最適なパターンである。 この証明では空白は考慮していないので正確でない
しかし、多分根幹をこれとして正しく証明できそうな予感はする
メモ
示したいもの
改行する必要がなければ、改行せずに文字列を一つ一つ挿入していくような方法でも最適解$ f(W)行が得られること。
つまり
制約「任意の1行の幅 < $ W」が満たされるどのような改行方法でも、必ず$ f(W) - 1以上回の改行を挟まなければならない
or
$ f(W) - 1回以下の改行では必ず制約「任意の1行の幅 $ \leq W」を破る行が存在する
のどっちかを示せばいい
改行する必要があるとは
単語$ Lを追記する際に
$ W-l文字がすでにその行に入っていて
文字数について$ l < Lであるような場合
全ての最適解は、「ある単語で改行する必要がないのに改行した最適解」と「改行する必要がないので改行しなかった最適解」に分けられる。
ある「ある単語で改行する必要がないのに改行した解」$ Aが最適解であったとする。
$ Aの余分な改行から再度改行を挟み直しても、その改行は元の解$ Aの改行の個数以下になる